<template><div><h3 id="模板" tabindex="-1"><a class="header-anchor" href="#模板"><span>模板</span></a></h3>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#7F848E;font-style:italic">// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1</span></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// ph[k]存储第k个插入的点在堆中的位置</span></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// hp[k]存储堆中下标是k的点是第几个插入的</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">[N], </span><span style="color:#E5C07B">ph</span><span style="color:#ABB2BF">[N], </span><span style="color:#E5C07B">hp</span><span style="color:#ABB2BF">[N], Size;</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// 交换两个点，及其映射关系</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> heap_swap</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> a</span><span style="color:#ABB2BF">, </span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> b</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#61AFEF">    swap</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">ph</span><span style="color:#ABB2BF">[</span><span style="color:#E5C07B">hp</span><span style="color:#ABB2BF">[a]],</span><span style="color:#E5C07B">ph</span><span style="color:#ABB2BF">[</span><span style="color:#E5C07B">hp</span><span style="color:#ABB2BF">[b]]);</span></span>
<span class="line"><span style="color:#61AFEF">    swap</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">hp</span><span style="color:#ABB2BF">[a], </span><span style="color:#E5C07B">hp</span><span style="color:#ABB2BF">[b]);</span></span>
<span class="line"><span style="color:#61AFEF">    swap</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">h</span><span style="color:#ABB2BF">[a], </span><span style="color:#E5C07B">h</span><span style="color:#ABB2BF">[b]);</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> down</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> u</span><span style="color:#ABB2BF">)</span></span>
<span class="line"><span style="color:#ABB2BF">{</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> t </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> u;</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (u </span><span style="color:#C678DD">*</span><span style="color:#D19A66"> 2</span><span style="color:#C678DD"> &#x3C;=</span><span style="color:#ABB2BF"> size </span><span style="color:#56B6C2">&#x26;&#x26;</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">[u </span><span style="color:#C678DD">*</span><span style="color:#D19A66"> 2</span><span style="color:#ABB2BF">] </span><span style="color:#C678DD">&#x3C;</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">[t]) t </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> u </span><span style="color:#C678DD">*</span><span style="color:#D19A66"> 2</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (u </span><span style="color:#C678DD">*</span><span style="color:#D19A66"> 2</span><span style="color:#C678DD"> +</span><span style="color:#D19A66"> 1</span><span style="color:#C678DD"> &#x3C;=</span><span style="color:#ABB2BF"> size </span><span style="color:#56B6C2">&#x26;&#x26;</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">[u </span><span style="color:#C678DD">*</span><span style="color:#D19A66"> 2</span><span style="color:#C678DD"> +</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">] </span><span style="color:#C678DD">&#x3C;</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">[t]) t </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> u </span><span style="color:#C678DD">*</span><span style="color:#D19A66"> 2</span><span style="color:#C678DD"> +</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF"> (u </span><span style="color:#C678DD">!=</span><span style="color:#ABB2BF"> t)</span></span>
<span class="line"><span style="color:#ABB2BF">    {</span></span>
<span class="line"><span style="color:#61AFEF">        heap_swap</span><span style="color:#ABB2BF">(u, t);</span></span>
<span class="line"><span style="color:#61AFEF">        down</span><span style="color:#ABB2BF">(t);</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"></span>
<span class="line"><span style="color:#7F848E;font-style:italic">// O(n)建堆</span></span>
<span class="line"><span style="color:#C678DD">for</span><span style="color:#ABB2BF"> (</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> n </span><span style="color:#C678DD">/</span><span style="color:#D19A66"> 2</span><span style="color:#ABB2BF">; i; i </span><span style="color:#C678DD">--</span><span style="color:#ABB2BF"> ) </span><span style="color:#61AFEF">down</span><span style="color:#ABB2BF">(i);</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h3 id="堆排序" tabindex="-1"><a class="header-anchor" href="#堆排序"><span>堆排序</span></a></h3>
<p><img src="@source/notes/基础算法/2.数据结构/4-2.png" alt=""></p>
<h4 id="输入样例" tabindex="-1"><a class="header-anchor" href="#输入样例"><span>输入样例</span></a></h4>
<div class="language-plain line-numbers-mode" data-highlighter="shiki" data-ext="plain" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span>5 3</span></span>
<span class="line"><span>4 5 1 3 2</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="输出样例" tabindex="-1"><a class="header-anchor" href="#输出样例"><span>输出样例</span></a></h4>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#D19A66">1</span><span style="color:#D19A66"> 2</span><span style="color:#D19A66"> 3</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div></div></div><h4 id="参考答案" tabindex="-1"><a class="header-anchor" href="#参考答案"><span>参考答案</span></a></h4>
<div class="language-cpp line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="cpp" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> N </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">5</span><span style="color:#C678DD">+</span><span style="color:#D19A66">10</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#E5C07B"> heap</span><span style="color:#ABB2BF">[N],Size;</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> down</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> i</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> t </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> i;</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF">(</span><span style="color:#D19A66">2</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">i</span><span style="color:#C678DD">&#x3C;=</span><span style="color:#ABB2BF">Size</span><span style="color:#56B6C2">&#x26;&#x26;</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[t]</span><span style="color:#C678DD">></span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[</span><span style="color:#D19A66">2</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">i]) t </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 2</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">i;</span><span style="color:#7F848E;font-style:italic"> // 如果左孩子节点存在并且不是最值的话</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF">(</span><span style="color:#D19A66">2</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">i</span><span style="color:#C678DD">+</span><span style="color:#D19A66">1</span><span style="color:#C678DD">&#x3C;=</span><span style="color:#ABB2BF">Size</span><span style="color:#56B6C2">&#x26;&#x26;</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[t]</span><span style="color:#C678DD">></span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[</span><span style="color:#D19A66">2</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">i</span><span style="color:#C678DD">+</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">]) t </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 2</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">i</span><span style="color:#C678DD">+</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">;</span><span style="color:#7F848E;font-style:italic"> // 如果右孩子节点存在并且不是最值的话</span></span>
<span class="line"><span style="color:#C678DD">    if</span><span style="color:#ABB2BF">(i </span><span style="color:#C678DD">!=</span><span style="color:#ABB2BF"> t){</span></span>
<span class="line"><span style="color:#61AFEF">        swap</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[i],</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[t]);</span><span style="color:#7F848E;font-style:italic"> // 交换</span></span>
<span class="line"><span style="color:#61AFEF">        down</span><span style="color:#ABB2BF">(t);</span><span style="color:#7F848E;font-style:italic">  // 递归处理子树</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n,m;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">m;Size </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> n;</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">;i </span><span style="color:#C678DD">&#x3C;=</span><span style="color:#ABB2BF"> n;i</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">) cin</span><span style="color:#C678DD">>></span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[i];</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> n</span><span style="color:#C678DD">/</span><span style="color:#D19A66">2</span><span style="color:#ABB2BF">;i </span><span style="color:#C678DD">></span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;i</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">) </span><span style="color:#61AFEF">down</span><span style="color:#ABB2BF">(i);</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(m</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#ABB2BF">        cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">]</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">" "</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#61AFEF">        swap</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">],</span><span style="color:#E5C07B">heap</span><span style="color:#ABB2BF">[Size</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">]);</span><span style="color:#7F848E;font-style:italic">// 每次都和最后一位元素进行交换</span></span>
<span class="line"><span style="color:#61AFEF">        down</span><span style="color:#ABB2BF">(</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">);</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    return</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h3 id="模拟堆" tabindex="-1"><a class="header-anchor" href="#模拟堆"><span>模拟堆</span></a></h3>
<p><img src="@source/notes/基础算法/2.数据结构/4-2.png" alt=""></p>
<h4 id="输入样例-1" tabindex="-1"><a class="header-anchor" href="#输入样例-1"><span>输入样例</span></a></h4>
<div class="language-plain line-numbers-mode" data-highlighter="shiki" data-ext="plain" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span>8</span></span>
<span class="line"><span>I -10</span></span>
<span class="line"><span>PM</span></span>
<span class="line"><span>I -10</span></span>
<span class="line"><span>D 1</span></span>
<span class="line"><span>C 2 8</span></span>
<span class="line"><span>I 6</span></span>
<span class="line"><span>PM</span></span>
<span class="line"><span>DM</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="输出样例-1" tabindex="-1"><a class="header-anchor" href="#输出样例-1"><span>输出样例</span></a></h4>
<div class="language-plain line-numbers-mode" data-highlighter="shiki" data-ext="plain" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span>-10</span></span>
<span class="line"><span>6</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="参考答案-1" tabindex="-1"><a class="header-anchor" href="#参考答案-1"><span>参考答案</span></a></h4>
<div class="language-cpp line-numbers-mode" data-highlighter="shiki" data-ext="cpp" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div></div></div></div></template>


